package com.linchong.linkedlist.medium;

import com.linchong.linkedlist.basic.BasicLinkList;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-30 19:47
 * @Description: 反转链表II。
 *
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 */
@SuppressWarnings("unused")
public class reverseBetween extends BasicLinkList {


	/**
	 * 找到需要逆置的节点和其前节点
	 *
	 * 逆置m~n节点
	 *
	 * 记录节点n
	 *
	 * 处理前置节点和后置节点的指向
	 *
	 * @param head
	 * @param m
	 * @param n
	 * @return
	 */
	public ListNode reverseBetween(ListNode head, int m, int n) {
		// 计算需要逆置节点长度
		int changeLen = n-m+1;
		//初始化开始逆置节点的前驱
		ListNode preHead=null;
		// 最终转换的链表头指针
		ListNode res = head;
		// m-1,移动位置
		while(head!=null && m-1>0){
			m--;
			//记录head的前驱
			preHead = head;
			head = head.next;
		}

		//将modify_list_tail指向head,即逆置后的链表尾
		ListNode modifyListTail = head;
		//逆置change_len个节点
		ListNode newHead = null;
		while(head !=null&&changeLen!=0){
			ListNode next = head.next;
			head.next = newHead;
			newHead = head;
			head = next;
			//没完成一个节点，change_len减一
			changeLen--;
		}
		modifyListTail.next = head;

		//preHead非空，不是第一个
		if(preHead!=null){
			preHead.next = newHead;
		}
		//preHead是第一个元素
		else{
			res = newHead;
		}
		return res;
	}


}
